/**
 * 746. 使用最小花费爬楼梯
 * https://leetcode-cn.com/problems/min-cost-climbing-stairs/
 */
public class Solutions_746 {
    public static void main(String[] args) {
//        int[] cost = {10, 15, 20};  // output: 15
        // 解释: 最低花费是从cost{1}开始，然后走两步即可到阶梯顶，一共花费15。

        int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};  // output: 6
        // 解释: 最低花费方式是从cost{0}开始，逐个经过那些1，跳过cost{3}，一共花费6。

        int result = minCostClimbingStairs(cost);
        System.out.println(result);
    }

    public static int minCostClimbingStairs(int[] cost) {
        if (cost == null) {
            return 0;
        }
        int first = cost[0], second = cost[1];
        for (int i = 2; i < cost.length; i++) {
            // [0, i] 的花费 = i - 1 + cost[i] 或者 i - 2 + cost[i]
            int cur = Math.min(first + cost[i], second + cost[i]);
            first = second;
            second = cur;
        }
        return Math.min(first, second);
    }
}
